The purpose of this research project is to determine the safety and toxicity (side effects) of an experimental cancer vaccine, to observe the vaccine+s effects on the immune system, and to note any effects of the vaccine on prostate cancer (as measured by the PSA blood test). The dose of virus in the vaccination will be increased in groups of three patients each to determine the immune response to the vaccine. The vaccine is derived from the same virus material that was used for many years to vaccinate against smallpox. The virus is called vaccinia. Some human genetic material (DNA) has been put inside of the virus. The human DNA that is put inside produces a protein (or chemical) on the surface of some normal and some cancer cells from the prostate. This protein is called prostate specific antigen (PSA). This procedure of "recombining" viral and human DNA makes what is called a recombinant vaccinia virus (or Prostvac, for short).